package com.peng.stack_queue.tests;

import java.util.Objects;
import java.util.Stack;

/**
 * 提供一个特殊的栈，除了基础功能之外，支持时间复杂度O（1）的得到当前栈中最小的数
 * 注：可以使用现成的栈结构
 *
 * 与另外一个不同之处在于：
 * 牺牲了一些时间复杂度，去换取减少空间复杂度
 * 只有当min栈顶元素<=push元素的时候，才放入栈顶
 * 当pop时，也只有当min与data栈顶的元素相同时，在pop data栈顶的时候，才同时pop掉min栈顶
 *
 */
public class GetMinValueAbleStackVer2 {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public GetMinValueAbleStackVer2() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }


    public void push(int val) {
        dataStack.push(val);
        if (minStack.isEmpty()) {
            minStack.push(val);
            return;
        }

        if(minStack.peek()>=val){
            minStack.push(val);
        }

    }

    public Integer pop() {
        if(dataStack.isEmpty()){
            return null;
        }
        Integer popNum = dataStack.pop();
        if(Objects.equals(popNum, minStack.peek())){
            minStack.pop();
        }

        return popNum;
    }

    public int getMin(){
        return minStack.peek();
    }

    public static void main(String[] args) {
        GetMinValueAbleStackVer2 stack = new GetMinValueAbleStackVer2();
        stack.push(4);
        stack.push(3);
        stack.push(5);
        stack.push(4);
        stack.push(9);
        stack.push(1);

        System.out.println(stack.getMin());
        stack.pop();
        System.out.println(stack.getMin());
        
    }

}
